/*
 * Created on Jun 11, 2005
 */
package clustering.implementations;

import java.util.*;
import org.w3c.dom.*;
import clustering.framework.*;

/**
 * @author Tudor.Ionescu@supelec.fr

FlatTreeScorer

This class is an implementation of the flat tree scoring based on the calculation of the average distance between the elements of the same clusters. This class computes the score of a tree obtained through K-Means clustering.

 */
public class FlatTreeScorer implements IClusterTreeScorer{
	public double ComputeScore(Document xmlTree, double [][] dMatrix){
		// create the full list of distinct distances
		DMElement [] dmeList = new DMElement[sum(dMatrix.length)];
		int count = 0;
		for(int i=0;i<dMatrix.length;i++){
			for(int j=i+1;j<dMatrix.length;j++){
				dmeList[count++] = new DMElement(i,j,dMatrix[i][j]);
			}
		}		
		Arrays.sort(dmeList);
		
		// compute the number of distances in the current tree
		Node root = xmlTree.getFirstChild();
		double embedded_dist = 0;
		int embedded_count = 0;
		for(int i=0;i<root.getChildNodes().getLength();i++){
			Node branch = root.getChildNodes().item(i);
			int [] branchElemList = new int[branch.getChildNodes().getLength()];
			embedded_count += sum(branchElemList.length);
			for(int j=0;j<branch.getChildNodes().getLength();j++){
				Node elem = branch.getChildNodes().item(j);
				for(int k=0;k<elem.getAttributes().getLength();k++){
					Node attrib = elem.getAttributes().item(k);
					if(attrib.getNodeName().toLowerCase()=="id"){
						branchElemList[j] = Integer.parseInt(attrib.getNodeValue());
						break;
					}
				}
			}
			embedded_dist += computeBranchDistance(branchElemList,dMatrix);
		}
		double min_dist = 0, max_dist = 0;
		for(int i=0;i<embedded_count;i++){
			max_dist += dmeList[i].dist;
			min_dist += dmeList[dmeList.length - 1 - i].dist;
		}
		
		return (max_dist - embedded_dist)/(max_dist - min_dist);
	}
	double computeBranchDistance(int [] bel, double [][] dm){
		double dist = 0;
		for(int i=0;i<bel.length;i++){
			for(int j=i+1;j<bel.length;j++){
				dist += dm[bel[i]][bel[j]];
			}
		}
		return dist;
	}
	int sum(int n){
		int s = 0;
		for(int i=0;i<n;i++){
			s += i;
		}
		return s;
	}
}
